package liangtWorkSpace.suanfa;


import java.util.HashMap;

public class ListRandomNode {
    public static class Node{
        Node next;
        Node rand;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 克隆复杂链表
     * @param node
     * @return
     */
    public  static Node clone1(Node node){
        Node cur = node;

        HashMap<Node,Node> map = new HashMap();
        while (cur != null){
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        cur = node;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(node);
    }

    public static Node clone2(Node head){
        Node cur = head;

        Node next = null;

        /**
         * 创建副本在原链表之后
         */
        while (cur != null){
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }

        /**
         * 将所有的副本节点都赋值rand
         */
        Node curCopy = null;
        while (cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand == null ? null: cur.rand.next;
            cur = next;
        }

        Node res = cur.next;

        /**
         * 将所有新节点选出来
         */
        while (cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.next = next != null ? next.next:null;
            cur = next;
        }
        return res;
    }

    /**
     * 环行链表，获取环点
     * @return
     */
    public static Node getNode(Node head){
        //小于3个的链无环
        if(head == null || head.next ==null || head.next.next == null){
            return null;
        }
        // n1 慢 n2 快
        Node n1 = head.next;
        Node n2 = head.next.next;

        //如果快慢重合则必有环
        while (n1 != n2){
            if (n1 == null || n2 == null || n2.next == null || n2.next.next == null){
                return null;
            }
            n1 = n1.next;
            n2 = n2.next.next;
        }

        //逐步循环，两节点相遇则相遇点就是环入口
        n2 = head;
        while (n1 != n2){
            n1 = n1.next;
            n2 = n2.next;
        }

        return n1;
    }
}
